{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Subarray Product Less Than K"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numSubarrayProductLessThanK"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #乘积小于 K 的子数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "给你一个整数数组 <code>nums</code> 和一个整数 <code>k</code> ，请你返回子数组内所有元素的乘积严格小于<em> </em><code>k</code> 的连续子数组的数目。\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [10,5,2,6], k = 100\n",
    "<strong>输出：</strong>8\n",
    "<strong>解释：</strong>8 个乘积小于 100 的子数组分别为：[10]、[5]、[2],、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。\n",
    "需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3], k = 0\n",
    "<strong>输出：</strong>0</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:&nbsp;</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 3 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= k &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [subarray-product-less-than-k](https://leetcode.cn/problems/subarray-product-less-than-k/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [subarray-product-less-than-k](https://leetcode.cn/problems/subarray-product-less-than-k/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[10,5,2,6]\\n100', '[1,2,3]\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        left = 0\n",
    "        windowproduct = 1\n",
    "        total = 0\n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            windowproduct *= nums[i]\n",
    "            while left <= i and windowproduct >= k:\n",
    "                windowproduct //= nums[left]\n",
    "                left += 1\n",
    "            total += i - left + 1\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        i = j = 0\n",
    "        p = 1\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "\n",
    "        if k <= 1:\n",
    "            return 0\n",
    "\n",
    "        while j < n:\n",
    "            if nums[j] >= k:\n",
    "                j += 1\n",
    "                i = j\n",
    "                p = 1\n",
    "                continue\n",
    "\n",
    "            p *= nums[j]\n",
    "            while p >= k:\n",
    "                p //= nums[i]\n",
    "                i += 1\n",
    "            res += j - i + 1\n",
    "            j += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        left,right = 0,0\n",
    "        mul = 1\n",
    "        ans =0\n",
    "        for right in range(len(nums)):\n",
    "            mul *= nums[right]\n",
    "            while(left<=right and mul>=k):\n",
    "                mul /= nums[left]\n",
    "                left += 1\n",
    "            ans += right-left+1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        res = 0\n",
    "        i, j = 0, 0\n",
    "        p = 1\n",
    "        while j < len(nums):\n",
    "            p *= nums[j]\n",
    "            j += 1\n",
    "            while p >= k:\n",
    "                if i == len(nums):\n",
    "                    return res\n",
    "                p //= nums[i]\n",
    "                i += 1\n",
    "            res += j - i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums, k):\n",
    "        if k <= 1:\n",
    "            return 0 \n",
    "        cnt = 0\n",
    "        t = 1\n",
    "        i = 0\n",
    "        for j in range(len(nums)):\n",
    "            t *= nums[j]\n",
    "            while t >= k:\n",
    "                t //= nums[i]\n",
    "                i += 1\n",
    "            cnt += (j - i + 1)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        i = j = 0\n",
    "        p = 1\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "\n",
    "        if k <= 1:\n",
    "            return 0\n",
    "\n",
    "        while j < n:\n",
    "            if nums[j] >= k:\n",
    "                j += 1\n",
    "                i = j\n",
    "                p = 1\n",
    "                continue\n",
    "\n",
    "            p *= nums[j]\n",
    "            while p >= k:\n",
    "                p //= nums[i]\n",
    "                i += 1\n",
    "            res += j - i + 1\n",
    "            j += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        i = j = 0\n",
    "        p = 1\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "\n",
    "        if k <= 1:\n",
    "            return 0\n",
    "\n",
    "        while j < n:\n",
    "            if nums[j] >= k:\n",
    "                j += 1\n",
    "                i = j\n",
    "                p = 1\n",
    "                continue\n",
    "\n",
    "            p *= nums[j]\n",
    "            while p >= k:\n",
    "                p //= nums[i]\n",
    "                i += 1\n",
    "            res += j - i + 1\n",
    "            j += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def func(n):\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        else:\n",
    "            n*Solution.func(n-1)\n",
    "    def numSubarrayProductLessThanK(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        nums = tuple(nums)\n",
    "        i = 0\n",
    "        j = 0\n",
    "        count = 0\n",
    "        result = 1\n",
    "        while j < len(nums):\n",
    "            result *= nums[j]\n",
    "            while result >= k:\n",
    "                if i == len(nums):\n",
    "                    return count\n",
    "                result /= nums[i]\n",
    "                i +=1\n",
    "            count += j-i+1\n",
    "            j += 1\n",
    "        return count\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    print(Solution.numSubarrayProductLessThanK(None, [10,5,2,6], 100))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "#         count = 0\n",
    "#         for i in range(len(nums)):\n",
    "#             j = i + 1\n",
    "#             multi = nums[i]\n",
    "#             while multi < k and j <= len(nums):\n",
    "#                 count += 1\n",
    "#                 if j < len(nums):\n",
    "#                     multi *= nums[j]\n",
    "#                 j += 1\n",
    "        \n",
    "#         return count\n",
    "        if k <= 1: return 0\n",
    "        prod = 1\n",
    "        ans = left = 0\n",
    "        for right, val in enumerate(nums):\n",
    "            prod *= val\n",
    "            while prod >= k:\n",
    "                prod /= nums[left]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        left, right = 0, 0\n",
    "        n = len(nums)\n",
    "        product = 1\n",
    "        cnt = 0\n",
    "        left = 0\n",
    "        for right, val in enumerate(nums):\n",
    "            product *= val\n",
    "            while product >= k and left <= right:\n",
    "                product /= nums[left]\n",
    "                left += 1\n",
    "            cnt += right-left + 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if k <= 1: return 0\n",
    "        prod = 1\n",
    "        ans = left = 0\n",
    "        for right, val in enumerate(nums):\n",
    "            prod *= val\n",
    "            while prod >= k:\n",
    "                prod /= nums[left]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if k <= 1: return 0\n",
    "        prod = 1\n",
    "        ans = left = 0\n",
    "        for right, val in enumerate(nums):\n",
    "            prod *= val\n",
    "            while prod >= k:\n",
    "                prod /= nums[left]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef numSubarrayProductLessThanK(self, nums, k):\n",
    "\t\tcount = 0\n",
    "\t\ttimes = 1\n",
    "\t\tindex = 0\n",
    "\t\tstartIndex = 0\n",
    "\t\tif nums[len(nums) - 1] < k: count += 1\n",
    "\t\twhile len(nums) != 0:\n",
    "\t\t\tif nums[0] < k:\n",
    "\t\t\t\tfor index in range(startIndex, len(nums)):\n",
    "\t\t\t\t\ttimes *= nums[index]\n",
    "\t\t\t\t\tif times < k: count += 1\n",
    "\t\t\t\t\telse: break\n",
    "\t\t\t\ttimes /= nums[0] * nums[index]\n",
    "\t\t\t\tcount += index - 1\n",
    "\t\t\t\tstartIndex = index - 1\n",
    "\t\t\tnums.remove(nums[0])\n",
    "\t\treturn count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        res = 0\n",
    "        left, right = 0, 0\n",
    "        tmp = 1\n",
    "        while right < len(nums):\n",
    "            tmp *= nums[right]\n",
    "            while left <= right and tmp >= k:\n",
    "                tmp /= nums[left]\n",
    "                left += 1\n",
    "            res += right - left + 1\n",
    "            right += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if k == 0:return 0\n",
    "        left,right = 0,0\n",
    "        temp,res = 1,0\n",
    "        while left<len(nums) and right<len(nums):\n",
    "            temp *= nums[right]\n",
    "            while left<=right and temp>=k:\n",
    "                temp//=nums[left]\n",
    "                left += 1\n",
    "            \n",
    "            res += right - left +1\n",
    "            right += 1\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if k < 2:\n",
    "            return 0\n",
    "        m, ans = 1, 0\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            m *= nums[i]\n",
    "            while m >= k:\n",
    "                m //= nums.pop()\n",
    "                continue\n",
    "            ans += len(nums) - i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if k<=1:\n",
    "            return 0\n",
    "        ans = 0\n",
    "        p = 1\n",
    "        left = 0\n",
    "        for right,x in enumerate(nums):\n",
    "            p *= x\n",
    "            while p >= k:\n",
    "                p /= nums[left]\n",
    "                left += 1\n",
    "            ans += right-left+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        if k<=1:return 0\n",
    "        ans=0\n",
    "        l=0\n",
    "        tmp=1\n",
    "        for i in range(len(nums)):\n",
    "            tmp*=nums[i]\n",
    "            while tmp>=k:\n",
    "                tmp/=nums[l]\n",
    "                l+=1\n",
    "            ans+=i-l+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        i = 0\n",
    "        length = len(nums)\n",
    "        result = 0\n",
    "        chengji = 1\n",
    "        if k <= 1:\n",
    "            return 0\n",
    "        for j, num in enumerate(nums):\n",
    "            chengji *= num\n",
    "            while chengji >= k:\n",
    "                chengji /= nums[i]\n",
    "                i += 1\n",
    "            result += j - i + 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        multi = 1\n",
    "        left_index = 0\n",
    "        ans = 0\n",
    "\n",
    "        if k <= 0:\n",
    "            return 0\n",
    "\n",
    "        for right in range(0, len(nums)):\n",
    "            multi *= nums[right]\n",
    "\n",
    "            while multi >= k and left_index <= right:\n",
    "                multi = multi / nums[left_index]\n",
    "                left_index += 1\n",
    "\n",
    "\n",
    "            if multi < k:\n",
    "                ans += (right - left_index + 1)\n",
    "                print(ans, right, right - left_index + 1, multi)\n",
    "            \n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        slow, fast, prod, cnt = 0, 0, 1, 0\n",
    "        while fast < len(nums):\n",
    "            prod *= nums[fast]\n",
    "            while fast >= slow and prod >= k:\n",
    "                prod //= nums[slow]\n",
    "                slow += 1\n",
    "            if fast >= slow and prod < k:\n",
    "                cnt += fast - slow + 1\n",
    "            fast += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        i,j = 0,0\n",
    "        res = 0\n",
    "        x = 1\n",
    "        while(j<len(nums)):\n",
    "            x *= nums[j]\n",
    "            if x<k:\n",
    "                res += j-i+1\n",
    "            else:\n",
    "                while(i<=j and x>=k):\n",
    "                    x /= nums[i]\n",
    "                    i += 1\n",
    "                res += j-i+1\n",
    "            j += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:\n",
    "        res, left = 1, 0\n",
    "        ans = 0\n",
    "        for right in range(len(nums)):\n",
    "            res *= nums[right]\n",
    "            while res >= k and left <= right:\n",
    "                res /= nums[left]\n",
    "                left += 1\n",
    "            ans += right - left + 1\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
